\documentclass{article}
  \usepackage{amsmath}
  \usepackage{amssymb}
\begin{document}

\begin{enumerate}
  \item Consider permutaion
  $\sigma = \bigl(\begin{smallmatrix}
    1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 6 & 4 & 5 & 1 & 2
    \end{smallmatrix} \bigr)$
  and $\tau = \bigl(\begin{smallmatrix}
    1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 6 & 5 & 3 & 1
    \end{smallmatrix} \bigr)$ in $S_6$.

    Find: i. composition $\tau \circ \sigma$, ii. $\sigma^{-1}$.

    \item Consider functions $f: A\to B$ and $g: B\to C$. Prove the following:

    a. If $f$ and $g$ are one-to-one, then $g\circ f$ is one-to-one.

    b. If $f$ and $g$ are onto functions, then $g\circ f$ is an onto function.

    \item Prove the following generalization of DeMorgan's law: For any class of sets $\{A_i\}$ we have
    $$
    (\cup_i A_i)^\mathsf{c} = \cap_i A_i^\mathsf{c}
    $$

    \item Show that the set $\textbf{Z}$ of integers has cardinality $\aleph_0$.

    \item Let $A_1, A_2, \cdots$ be a countable number of finite sets.
    Prove that the union $S = \cup_i S_i$ is countable.

    \item Prove: A countable union of countable sets is countable.

    \item Prove: The set $\textbf{I}$ of all real numbers between 0 and 1 inclusive is uncountable.

    \item For any $n \in \textbf{N}$, let $D_n = (0, 1/n)$, the open iterval from $0$ to $1/n$. Find:

    i. $D_3 \cup D_4$, ii. $D_3 \cup D_20$, iii. $D_s \cup D_t$, iv. $D_s \cup D_t$

    \item Suppose $P(n) = a_0 + a_1 n + a_2 n^2 + \cdots + a_m n^m$ has degree $m$. Prove $P(n) = O(n^m)$

    \item Prove: $|A| < |\textrm{Power}(A)|$ (where $\textrm{Power}(A)$ is the power set of $A$).

    \item Prove the following equivalent formulation of the Schroeder-Bernstein Theorem:

    Suppose $X\supseteq Y \supseteq X_1$ and $X\simeq X_1$, then $X\simeq Y$.

    \item Prove: Suppose $f: A \to B$ and $g: B \to A$ satisfy $g\circ f = 1_A$. Then $f$ is one-to-one and $g$ is onto.

    \item Prove: A function $f: A\to B$ is invertible if and only if $f$ is both one-to-one and onto.

    \item Prove: Suppose $f: A\to B$ is invertible with inverse function $f^{-1}: B\to A$.
    Then $f^{-1}\circ f = 1_A$ and $f\circ f^{-1} = 1_B$.

    \item Suppose $f: A\to B$ is one-to-one and $g: A\to B$ is onto. Let $x$ be a subset of $A$.

    i. Show $f 1_x$, the restriction of $f$ to $x$, is one-to-one.

    ii. Show $g 1_x$, need not be onto.

    \item For each $n \in N$, consider the open interval $A_n = (0, 1/n) = \{x | 0 < x < 1/n\}$. Find:

    a. $A_2 \cup A_8$; c. $\cup(A_i | i \in J)$; e. $\cup(A_i | i \in K)$;

    b. $A_3 \cap A_7$; d. $\cap(A_i | i \in J)$; f. $\cap(A_i | i \in K)$;

    where $J$ is a finite subset of $\textbf{N}$ and $K$ is an infinite subset of $\textbf{N}$.

    \item Consider an indexed class of sets $\{A_i | i \in I\}$, a set $\textbf{B}$ and an index $i_0$ in $\textbf{I}$.

    Prove: a. $B\cap (\cup_i A_i) = \cup_i(B\cap A_i)$;
    b. $\cap(A_i | i \in I)\subseteq A_{i_0} \subseteq \cup (A_i | i \in I)$

    \item Prove:

    a. Every infinite set $A$ contains a denumerable subset $D$.

    b. Each subset of a denumerable set is finite or denumerable.

    c. If $A$ and $B$ are denumerable, then $A\times B$ is denumerable.

    d. The set $\textbf{Q}$ of rational numbers is denumerable.

    \item Prove: a. $|A\times B| = |B\times A|$;
    b. $A\subseteq B \implies |A| \leq |B|$;
    c. $|A| = |B| \implies |P(A)| = |P(B)|$.

    \item Prove: The set $P$ of all polynomial $p(x) = a_0 + a_1 x + \cdots + a_m x^m $
    with integral coefficients(that is, where $a_0, a_1, \cdots, a_m$ are integers) is denumerable.
  \end{enumerate}

\end{document}
